HDU_5750

描述

A positive proper divisor is a positive divisor of a number n, excluding n itself. For example, 1, 2, and 3 are positive proper divisors of 6, but 6 itself is not.
Peter has two positive integers n and d. He would like to know the number of integers below n whose maximum positive proper divisor is d.

输入格式

There are multiple test cases. The first line of input contains an integer T (1≤T≤106), indicating the number of test cases. For each test case:

The first line contains two integers n and d (2≤n,d≤109).

输出格式

For each test case, output an integer denoting the answer.

样例

输入

9
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
100 13

输出

1
2
1
0
0
0
0
0
4

思路

数学证明如下：

若d为素数，k为整数，在所有d·k<=N的情况下，只有k为小于等于d的素数，才能保证d为最大因子。
若d为合数，令d=m·h，m为d的最小质因子，h=d/m；k为整数，则有 k·h·m<=N。当k为小于m的质数时，易证。
当k为小于m的合数或者k>m时，则不能保证d是最大因子。
证毕。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#define inf 0x3f3f3f3f
#define ll long long
#define mod 100000007
using namespace std;
int const N = 200005;
bool prime[N];
int pp[N],cnt=0;
//这是一个很棒的筛法，相比于普通的筛法，他省略了很多重复步骤。
void init(){
    memset(prime,1,sizeof(prime));
    prime[0]=0;prime[1]=0;
    for(int i=2;i<=N;i++){
        if(prime[i]){
            pp[cnt++]=i;
        }
        for(int j=0; j < cnt && i * pp[j] <= N ; j++ ){
            prime[i * pp[j]]=0;
            if(i % pp[j]==0)break;
        }
    }
 }
int slove(int n,int d){
    int ans=0;
    for(int i=0;i<cnt;i++){
        if(pp[i] * d >= n)return ans;
        ans++;
        if(d % pp[i]==0)return ans;
    }
    return ans;
 }
int main()
{
    int T;init();
    scanf("%d",&T);
    while(T--){
        int n,d;
        scanf("%d%d",&n,&d);
        printf("%d\n",slove(n,d));
    }
    return 0;
}